package AVLTree;

import binarysorttree.std01.BinarySortTreeTest;

public class AvlTreeTest {
    public static void main(String[] args) {
        int[] a = {10,11,7,6,8,9};
        AvlTree avlTree = new AvlTree();
        for (int i = 0; i < a.length; i++) {
            Node node = new Node(a[i]);
            avlTree.add(node);
        }
        avlTree.print();
        System.out.println("旋转左后：" + avlTree.leftHeight()+"旋转右后："+avlTree.rightHeight() + " 根："+avlTree.root.date);
    }

    static class AvlTree{
        Node root;
        public void add(Node node){
            if(null == root){
                root = node;
            }else {
                root.add(node);
            }
        }

        public int leftHeight(){
            if (root.left ==null){
                return 0;
            }else {
                return root.left.height();
            }
        }

        public int rightHeight(){
            if (root.right ==null){
                return 0;
            }else {
                return root.right.height();
            }
        }
        /**
         * 左旋转
         * 意味着 右边降级
         */
        @Deprecated
        public void leftContraSolem(){
            //原根节点发生变化
            Node oldRoot = new Node(root.date);
            //记录原根节点的左子树
            Node oldLeft = root.left;
            //将原先左子树 挂到 原root 上
            oldRoot.left = oldLeft;
            //拿要上章的根节点 的左节点 他需要挂到 原old 的右节点
            Node nodeLeft = root.right.left == null ? null : root.right.left;
            //上面的准备完事
            //开始转移 根 给原根的右节点
            root = root.right;
            //新根的左节点 = 原根节点
            root.left = oldRoot;
            if(root.left!=null){
                //将 原根右的左 给到新根左的右节点
                root.left.right = nodeLeft;
            }
        }


        /**
         * 查找要删除的key
         * @param date 目标值
         * @return 目标节点 没有为null
         */
        public Node findNode(int date){
            if(this.root == null){
                return null;
            }
            return this.root.findNode(date);
        }

        /**
         * 查找父节点
         * @param date 目标值
         * @return 父节点
         */
        public Node findParentNode(int date){
            if(this.root == null){
                return null;
            }
            return this.root.findParentNode(date);
        }

        /**
         * 中序遍历
         */
        public void print(){
            if(this.root == null){
                return;
            }
            this.root.printInorderTraversal(root);
        }

        /**
         * 删除节点
         * @param date 值
         * @return true 则删除成功
         */
        public int remove(int date){
            //找到对应的值 targetNode
            Node targetNode = this.findNode(date);
            //找到父节点 parentNode
            Node parentNode = this.root.findParentNode(date);
            //如果删没有 子节点 比如删 4 4 节点下
            if(targetNode.left == null && targetNode.right == null){
                if(parentNode!=null && parentNode.left!=null &&  parentNode.left.date == date ){
                    parentNode.left = null;
                    return 1;
                }else if(parentNode!=null && parentNode.right!=null && parentNode.right.date == date ){
                    parentNode.right = null;
                    return 1;
                }else if(parentNode == null && this.root.date == date){
                    this.root = null;
                    return 1;
                }
            }else if ( targetNode.left!=null && targetNode.right!=null){
                //双节点
                //找右边的树 最小的节点
                Node minRight = targetNode.right.findMinRight();
                remove(minRight.date);
                targetNode.date = minRight.date;
                return 1;
            }else {
                //单节点不为空
                //判断是父节点的左 还是右
                if( parentNode == null ){
                    this.root =  targetNode.left== null? targetNode.right:targetNode.left;
                    return 1;
                }else if( parentNode.right!=null && parentNode.right.date == targetNode.date ){
                    parentNode.right = targetNode.left== null? targetNode.right:targetNode.left;
                    return 1;
                }else if( parentNode.left!=null &&  parentNode.left.date == targetNode.date ){
                    parentNode.left = targetNode.left== null? targetNode.right:targetNode.left;
                    return 1;
                }
            }
            return 0;
        }
    }

    static class Node{
        int date;
        Node left;
        Node right;

        public Node(int date) {
            this.date = date;
        }

        /**
         *
         * @return 返回树的高度
         */
        public int height(){
           if( this.left!=null || this.right!=null ){
               int left = this.left == null ? this.right.height() : this.left.height();
               int right = this.right == null ? this.left.height() : this.right.height();
               int max = Math.max(left, right);
               return max+1;
           }else {
               return 1;
           }
        }

        public int leftHeight(){
            if(left == null){
               return 0;
            }else {
                return left.height();
            }
        }
        public int rightHeight(){
            if(right == null){
                return 0;
            }else {
                return right.height();
            }
        }

        /**
         * 左旋转
         */
        public void leftRevolve(){
            // 把根的重新new 一个新的
            Node node = new Node(date);
            // 把节点左 再挂新的上
            node.left = this.left;
            //把 right 的值 设置到当前节点
            this.date = right.date;
            // 将right 的left 节点 给到new的 右上
            node.right = right.left;
            // 把right 指向 right.right
            this.right = right.right;
            // 节点的left指向 新的node
            this.left = node;
        }

        /**
         * 右旋
         */
        public void rightRevolve(){
            // 把根的重新new 一个新的
            Node node = new Node(date);
            // 把节点右 再挂新的上
            node.right = this.right;
            //把 left 的值 设置到当前节点
            this.date = left.date;
            // 将left 的right 节点 给到new的 右上
            node.left = left.right;
            // 把left 指向 left.left
            this.left = left.left;
            // 节点的left指向 新的node
            this.right = node;
        }

        public Node findMinRight(){
            if(this.left == null){
                return this;
            }else {
                return this.left.findMinRight();
            }
        }

        /**
         * 查找node
         * @param date
         * @return 节点
         */
        public Node findNode(int date){
            if(this.date>date){
                if(null != this.left){
                    //左子树
                    return this.left.findNode(date);
                }else {
                    return null;
                }
            }else if(this.date<date){
                if(null != this.right){
                    //右子树
                    return this.right.findNode(date);
                }else {
                    return null;
                }
            }else {
                return this;
            }
        }

        public Node findParentNode(int date){
            if( (this.left!=null && this.left.date ==date)
                    ||  (this.right!=null && this.right.date ==date) ){
                return this;
            }else {
                if(this.date < date && this.right!=null ){
                    return this.right.findParentNode(date);
                }else if(this.date > date && this.left!=null ) {
                    return this.left.findParentNode(date);
                }else {
                    return null;
                }
            }
        }



        /**
         *  如添加的节点的值 大于当前节点值 则放右子树 右子树为空 则this.right = node
         * @param node 添加的node
         */
        public void add(Node node){
            if(null == node){
                return;
            }
            // 右子树
            if(node.date > this.date){
                if(null == this.right){
                    this.right = node;
                }else {
                    this.right.add(node);
                }
            }else {
                if(null == this.left){
                    this.left = node;
                }else {
                    this.left.add(node);
                }
            }
            if(this.rightHeight() - this.leftHeight() > 1 ){
                //左旋 一次可能 不会变为 平衡二叉
                //左旋的时候 需要判断 你即将变为根的 左子树 是否大于 即将变为根的右
                if(this.right.leftHeight()>this.right.rightHeight()){
                    this.right.rightRevolve();
                }
                this.leftRevolve();
                return;
            }
            if(this.leftHeight() - this.rightHeight() > 1 ){
                //右旋
                //右旋 一次可能 不会变为 平衡二叉
                //右旋的时候 需要判断 你即将变为根的 右子树 是否大于 即将变为根的左子树
                // 旋转的时候 可能 待处理的节点长度 大于 别的树的长度 那么就需要将大的树降级 也就是旋
                if(this.left.leftHeight() < this.left.rightHeight()){
                    this.left.leftRevolve();
                }
                this.rightRevolve();
                return;
            }
        }
        //中序遍历 左 根 右
        public void printInorderTraversal(Node node){
            if(null != node.left){
                printInorderTraversal(node.left);
            }
            System.out.print(node.date + "   ");
            if(null != node.right){
                printInorderTraversal(node.right);
            }
        }
    }





}

